package nav;


import java.awt.Point;
import java.awt.Rectangle;
import java.io.File;
import java.util.LinkedList;

import javax.xml.parsers.*;

import org.w3c.dom.*;

/**
 * This class should recognize which gesture was shown by the user.
 * 
 */
public class Recognizer {

	private int numPoints = 64;
	private int squareSize = 250;
	private double angleRange = 45;
	private double anglePrecision = 2;
	private double phi = 0.5 * (-1.0 + Math.sqrt(5.0));

	private LinkedList<Template> templates = new LinkedList<Template>();

	/**
	 * Creates the templates.
	 */
	public Recognizer() {
		/* load templates */
		DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
		LinkedList<Point> list1 = new LinkedList<Point>();
		LinkedList<Point> list2 = new LinkedList<Point>();
		LinkedList<Point> list4 = new LinkedList<Point>();
		LinkedList<Point> list5 = new LinkedList<Point>();

		try {
			DocumentBuilder builder = factory.newDocumentBuilder();
			Document g0 = builder.parse(new File("src/templates/caret.xml"));
			Document g1 = builder.parse(new File("src/templates/circle.xml"));
			Document g3 = builder.parse(new File("src/templates/leftbracket.xml"));
			Document g4 = builder.parse(new File("src/templates/rightbracket.xml"));
			
		
			NodeList n1 = g0.getElementsByTagName("Point");
			NodeList n2 = g1.getElementsByTagName("Point");
			NodeList n4 = g3.getElementsByTagName("Point");
			NodeList n5 = g4.getElementsByTagName("Point");
			

			/* read file and write to template */
			for (int i = 0; i < n1.getLength(); i++) {
				int x = new Integer(n1.item(i).getAttributes()
						.getNamedItem("X").getNodeValue());
				int y = new Integer(n1.item(i).getAttributes()
						.getNamedItem("Y").getNodeValue());
				list1.add(new Point(x, y));
			}
			/* read file and write to template */
			for (int i = 0; i < n2.getLength(); i++) {
				int x = new Integer(n2.item(i).getAttributes()
						.getNamedItem("X").getNodeValue());
				int y = new Integer(n2.item(i).getAttributes()
						.getNamedItem("Y").getNodeValue());
				list2.add(new Point(x, y));
			}
			/* read file and write to template */
			for (int i = 0; i < n4.getLength(); i++) {
				int x = new Integer(n4.item(i).getAttributes()
						.getNamedItem("X").getNodeValue());
				int y = new Integer(n4.item(i).getAttributes()
						.getNamedItem("Y").getNodeValue());
				list4.add(new Point(x, y));
			}
			/* read file and write to template */
			for (int i = 0; i < n5.getLength(); i++) {
				int x = new Integer(n5.item(i).getAttributes()
						.getNamedItem("X").getNodeValue());
				int y = new Integer(n5.item(i).getAttributes()
						.getNamedItem("Y").getNodeValue());
				list5.add(new Point(x, y));
			}
			
		} catch (Exception e) {
			System.out.println(e);
		}
		templates.add(new Template("home", list1, this));
		templates.add(new Template("refresh", list2, this));
		templates.add(new Template("back", list4, this));
		templates.add(new Template("forward", list5, this));
		
	}

	/**
	 * Recognize which gesture is shown.
	 * 
	 * @param points
	 */
	public String recognize(LinkedList<Point> points) { // candidate points
		points = resample(points, numPoints);
		points = rotateToZero(points);
		points = scaleToSquare(points, squareSize);
		points = translateToOrigin(points);

		int t = 0;
		double b = Double.POSITIVE_INFINITY;
		for (int i = 0; i < templates.size(); i++) {
			double d = distanceAtBestAngle(points, templates.get(i).getList(),
					-angleRange, +angleRange, anglePrecision);
			if (d < b) {
				b = d;
				t = i;
			}
		}
		/* return the correct gesture */
		return templates.get(t).getName();
	}

	/* helper methods */

	/**
	 * Resizes the given LinkedList's.
	 */
	public LinkedList<Point> resample(LinkedList<Point> points, int n) {
		double i = pathLength(points) / (n - 1); // interval length
		double d = 0.0;
		LinkedList<Point> newpoints = new LinkedList<Point>();
		newpoints.add(points.getFirst());
		for (int j = 1; j < points.size(); j++) {
			double dist = distance(points.get(j - 1), points.get(j));
			if ((d + dist) >= i) {
				double qx = points.get(j - 1).x + ((i - d) / dist)
						* (points.get(j).x - points.get(j).x);
				double qy = points.get(j - 1).y + ((i - d) / dist)
						* (points.get(j).y - points.get(j - 1).y);
				Point q = new Point(new Double(qx).intValue(), new Double(qy)
						.intValue());
				newpoints.add(q); // insert 'q' at position j in points s.t. 'q'
				// will be the next j
				d = 0.0;
			} else
				d += dist;
		}
		// sometimes we fall a rounding-error short of adding the last point, so
		// add it if so
		if (newpoints.size() == n - 1)
			newpoints.add(points.get(points.size() - 1));
		return newpoints;
	}

	/**
	 * Rotates the first point to zero.
	 * 
	 * @param points
	 * @return
	 */
	public LinkedList<Point> rotateToZero(LinkedList<Point> points) {
		Point c = centroid(points);
		double theta = Math.atan2(c.y - points.get(0).y, c.x - points.get(0).x);
		return rotateBy(points, -theta);
	}

	/**
	 * Calculates the center of the rotation.
	 * 
	 * @param points
	 * @return
	 */
	public Point centroid(LinkedList<Point> points) {
		int x = 0, y = 0;
		for (int i = 0; i < points.size(); i++) {
			x += points.get(i).x;
			y += points.get(i).y;
		}
		x /= points.size();
		y /= points.size();
		return new Point(x, y);
	}

	/**
	 * Rotates all other points in the list.
	 * 
	 * @param points
	 * @param theta
	 * @return
	 */
	private LinkedList<Point> rotateBy(LinkedList<Point> points, double theta) {
		Point c = centroid(points);
		LinkedList<Point> newpoints = new LinkedList<Point>();
		for (int i = 0; i < points.size(); i++) {
			double qx = (points.get(i).x - c.x) * Math.cos(theta)
					- (points.get(i).y - c.y) * Math.sin(theta) + c.x;
			double qy = (points.get(i).x - c.y) * Math.sin(theta)
					+ (points.get(i).y - c.y) * Math.cos(theta) + c.y;
			newpoints.add(new Point(new Double(qx).intValue(), new Double(qy)
					.intValue()));
		}
		return newpoints;
	}

	/**
	 * Scales the points to a given size.
	 * 
	 * @param points
	 * @param size
	 * @return
	 */
	public LinkedList<Point> scaleToSquare(LinkedList<Point> points, int size) {
		Rectangle b = boundingBox(points);
		LinkedList<Point> newpoints = new LinkedList<Point>();
		for (int i = 0; i < points.size(); i++) {
			double qx, qy;
			if (b.width == 0)
				qx = 0;
			else
				qx = points.get(i).x * (size / b.width);
			if (b.height == 0)
				qy = 0;
			else
				qy = points.get(i).y * (size / b.height);
			newpoints.add(new Point(new Double(qx).intValue(), new Double(qy)
					.intValue()));
		}
		return newpoints;
	}

	/**
	 * Returns the bounding box of the given points.
	 * 
	 * @param points
	 * @return
	 */
	private Rectangle boundingBox(LinkedList<Point> points) {
		int minX = Integer.MAX_VALUE, maxX = -Integer.MAX_VALUE, minY = +Integer.MAX_VALUE, maxY = -Integer.MAX_VALUE;
		for (int i = 0; i < points.size(); i++) {
			if (points.get(i).x < minX)
				minX = points.get(i).x;
			if (points.get(i).x > maxX)
				maxX = points.get(i).x;
			if (points.get(i).y < minY)
				minY = points.get(i).y;
			if (points.get(i).y > maxY)
				maxY = points.get(i).y;
		}
		return new Rectangle(minX, minY, maxX - minX, maxY - minY);
	}

	/**
	 * Translates the given points to the origin.
	 * 
	 * @param points
	 * @return
	 */
	public LinkedList<Point> translateToOrigin(LinkedList<Point> points) {
		Point c = centroid(points);
		LinkedList<Point> newpoints = new LinkedList<Point>();
		for (int i = 0; i < points.size(); i++) {
			int qx = points.get(i).x - c.x;
			int qy = points.get(i).y - c.y;
			newpoints.add(new Point(new Double(qx).intValue(), new Double(qy)
					.intValue()));
		}
		return newpoints;
	}

	private double distanceAtBestAngle(LinkedList<Point> points,
			LinkedList<Point> t, double a, double b, double threshold) {
		double x1 = phi * a + (1.0 - phi) * b;
		double f1 = distanceAtAngle(points, t, x1);
		double x2 = (1.0 - phi) * a + phi * b;
		double f2 = distanceAtAngle(points, t, x2);
		while (Math.abs(b - a) > threshold) {
			if (f1 < f2) {
				b = x2;
				x2 = x1;
				f2 = f1;
				x1 = phi * a + (1.0 - phi) * b;
				f1 = distanceAtAngle(points, t, x1);
			} else {
				a = x1;
				x1 = x2;
				f1 = f2;
				x2 = (1.0 - phi) * a + phi * b;
				f2 = distanceAtAngle(points, t, x2);
			}
		}
		return Math.min(f1, f2);
	}

	private double distanceAtAngle(LinkedList<Point> points,
			LinkedList<Point> t, double theta) {
		LinkedList<Point> newpoints = rotateBy(points, theta);
		return pathDistance(newpoints, t);
	}

	/**
	 * Calculates the distance between two paths.
	 * 
	 * @param pts1
	 * @param pts2
	 * @return
	 */
	private double pathDistance(LinkedList<Point> pts1, LinkedList<Point> pts2) {
		double d = 0.0;
		for (int i = 0; i <= pts1.size() - 1; i++) {
			try {
				d += distance(pts1.get(i), pts2.get(i));
			} catch (Exception e) {
			}
		}
		double r = d / pts1.size();
		return r;
	}

	/**
	 * Calculates the distance between two points.
	 * 
	 * @param p1
	 * @param p2
	 * @return
	 */
	private double distance(Point p1, Point p2) {
		int dx = p2.x - p1.x;
		int dy = p2.y - p1.y;
		return Math.sqrt(dx * dx + dy * dy);
	}

	private double pathLength(LinkedList<Point> points) {
		double d = 0.0;
		for (int i = 1; i < points.size(); i++)
			d += distance(points.get(i - 1), points.get(i));
		return d;
	}
}
